package com.cb2.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/sum-of-left-leaves/">左叶子之和(Sum of Left Leaves)</a>
 * <p>给定二叉树的根节点 root ，返回所有左叶子之和。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入: root = [3,9,20,null,null,15,7]
 *                      3
 *                    /  \
 *                   9    20
 *                       / \
 *                      15  7
 *      输出: 24
 *      解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
 *
 *  示例 2:
 *      输入: root = [1]
 *      输出: 0
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>节点数在 [1, 1000] 范围内</li>
 *     <li>-1000 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/8 17:07
 */
public class LC0404SumOfLeftLeaves_S {
    static class Solution {
        public int sumOfLeftLeaves(TreeNode root) {
            //return sumOfLeftLeavesByIterator(root);
            return sumOfLeftLeavesByRecursion(root);
        }

        private int sumOfLeftLeavesByIterator(TreeNode root) {
            if (root == null) {
                throw new IllegalArgumentException();
            }
            Queue<TreeNode> helper = new LinkedList<>();
            helper.offer(root);
            int result = 0;
            while (!helper.isEmpty()) {
                TreeNode currNode = helper.poll();
                if (currNode.left != null) {
                    // 判断其左子节点是否为叶子节点
                    if (isLeafNode(currNode.left)) {
                        result += currNode.left.val;
                    } else {
                        // 叶子节点没有子节点，再入队也无意义。当然入队也没问题，仅仅多一次循环
                        helper.offer(currNode.left);
                    }
                }
                if (currNode.right != null) {
                    //if (currNode.right.left == null && currNode.right.right == null) {
                    //
                    //} else {
                    //    helper.offer(currNode.right);
                    //}
                    // 叶子节点没有子节点，再入队也无意义。当然入队也没问题，仅仅多一次循环
                    if (!isLeafNode(currNode.right)) {
                        helper.offer(currNode.right);
                    }
                }
            }
            return result;
        }

        private int sumOfLeftLeavesByRecursion(TreeNode root) {
            if (root == null) {
                throw new IllegalArgumentException();
            }
            return dfs(root);
        }

        private int dfs(TreeNode currNode) {
            int ans = 0;
            if (currNode == null) {
                return ans;
            }
            if (currNode.left != null) {
                ans += isLeafNode(currNode.left) ? currNode.left.val : dfs(currNode.left);
                //if (isLeafNode(currNode.left)) {
                //    ans += currNode.left.val;
                //} else {
                //    ans += dfs(currNode.left);
                //}
            }
            if (currNode.right != null && !isLeafNode(currNode.right)) {
                ans += dfs(currNode.right);
            }
            return ans;
        }

        private boolean isLeafNode(TreeNode currNode) {
            return currNode.left == null && currNode.right == null;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);

        TreeNode root2 = new TreeNode(1);

        Solution solution = new Solution();
        System.out.println(solution.sumOfLeftLeaves(root1));
        System.out.println(solution.sumOfLeftLeaves(root2));
    }
}
